package com.lsa.letcode.the117.populateNextRightII;

import com.lsa.letcode.common.TreeLinkNode;

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
    	int levelCount = levelCount(root);
		for (int level = 1; level <= levelCount; level++) {
    		connectLevel(null, root, level, 1);
		}
    }
    
    private void connectLevel(TreeLinkNode parent, TreeLinkNode n, int level, int currentLevel){
    	if (n != null && currentLevel <= level){
    		if (level == currentLevel) {
    			if (parent != null){
    				TreeLinkNode next;
    				if (n == parent.left) {
    					next = parent.right;
    				}
    				else{ // (n === parent.right) 
    					next = null; 
    				}
    				while(next == null && parent.next != null){
						if (parent.next.left != null){
							next = parent.next.left;
						}
						else {
							next = parent.next.right;
						}
						parent = parent.next;
					}
					n.next = next;
    			}
    		}
    		else {
    			final int newLevel = ++currentLevel;
    			connectLevel(n, n.left, level, newLevel);
    			connectLevel(n, n.right, level, newLevel);
    		}
    	}
    }
    
//    private void printLevel(TreeLinkNode parent, TreeLinkNode n, int level, int currentLevel){
//    	if (n != null && currentLevel <= level){
//    		if (level == currentLevel) {
//    			System.out.print(String.format("%s->%s ", parent.val, n.val));
//    		}
//    		else {
//    			final int newLevel = ++currentLevel;
//    			printLevel(n, n.left, level, newLevel);
//    			printLevel(n, n.right, level, newLevel);
//    		}
//    	}
//    }
    
    private int levelCount(TreeLinkNode root){
    	if (root == null){
    		return 0;
    	}
    	else {
    		return 1 + Math.max(levelCount(root.left), levelCount(root.right));
    	}
    }
}